import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yang
 * Date: 2022-07-18
 * Time: 16:19
 */
public class QuickSort {
    private static void swap(int a, int b, int[] array) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            for (int j = 0; j < array.length-i-1; j++) {
                if(array[j] > array[j+1])
                    swap(j,j+1,array);//
            }
        }
    }

    public static void insertSort(int start,int end,int[] array){
        for (int i = start+1; i <= end; i++) {
            int tmp = array[i];
            int j;
            for (j = i-1; j >= 0; j--) {
                if (array[j] > tmp) array[j + 1] = array[j];
                else break;
            }
            array[j+1] = tmp;
        }
    }
    private static int getPrivot(int a,int b,int c,int[] array){
        if( array[a] <=  array[b]){
            if(array[b]<=array[c])return b;
            else{
                if (array[c]<= array[a])return  a;
                else return c;
            }
        }

        if( array[a] >=  array[b]){
            if( array[c] >=  array[a])return a;
            else{
                if( array[c] >=  array[b])return c;
                else return b;
            }
        }
        return -1;
    }
    public static void partition(int start,int end,int[] array){
        if(end - start < 7){//插入排序优化
            insertSort(start,end,array);
            return;
        }
        if(start >= end)return;

        int l = start,r = end;
        int privot = getPrivot(start,end,start+end>>1,array);
        swap(start,privot,array);
        int key = array[start];
        while(l < r){
            while(l < r && array[r] >= key)r--;
            array[l] = array[r];
            while(l < r && array[l] <= key)l++;
            array[r] = array[l];
        }

        array[l] = key;
        partition(start,l-1,array);
        partition(l+1,end,array);
    }

    public static void quickSort(int[] array){
        partition(0,array.length-1,array);
    }

    public static void main(String[] args) {
        int[] array = {-4,0,7,4,9,-5,-1,0,-7,-1};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}
